#include <iostream>
using namespace std;

/// @brief 链式队列节点
typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
} LinkNode;

/// @brief 链式队列
typedef struct
{
    LinkNode *front, *rear; // 队列的对头和队尾指针
} LinkQueue;

/// @brief 初始化队列（带头节点）
/// @param Q
void InitQueueWithHead(LinkQueue &Q)
{
    // 初始时，front 、rear都指向头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

/// @brief 判断队列是否为空
/// @param Q
/// @return
bool isEmptyWithHead(LinkQueue Q)
{
    if (Q.front == Q.rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 初始化队列（不带头结点）
/// @param Q
void InitQueue(LinkQueue &Q)
{
    Q.front = NULL;
    Q.rear = NULL;
}

/// @brief
/// @param Q
/// @return
bool isEmpty(LinkQueue Q)
{
    if (Q.front == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 新元素入队（带头节点）
/// @param Q
/// @param x
void EnQueueWithHead(LinkQueue &Q, int x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s; // 新节点插入到rear之后
    Q.rear = s;       // 修改表尾指针
}

/// @brief 新元素入队（不带头结点）
/// @param Q
/// @param x
void EnQueue(LinkQueue &Q, int x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if (Q.front == NULL)
    {                // 在空队列中插入第一个元素
        Q.front = s; // 修改对头队尾指针
        Q.rear = s;
    }
    else
    {
        Q.rear->next = s; // 新节点插入到rear节点之后
        Q.rear = s;       // 修改rear指针
    }
}

/// @brief 队头元素出队（不带头结点）
/// @param Q
/// @param x
/// @return
bool DeQueueWithHead(LinkQueue &Q, int &x)
{
    if (Q.front == Q.rear)
    { // 空队
        return false;
    }
    LinkNode *p = Q.front->next;
    x = p->data;             // 用变量x返回队头元素
    Q.front->next = p->next; // 修改头结点的next指针
    if (Q.rear == p)         // 此次是最后一个节点出队
    {
        Q.rear = Q.front; // 修改rear指针
        free(p);          // 释放节点空间
        return true;
    }
}

/// @brief 对头元素出队（不带头结点）
/// @param Q
/// @param x
/// @return
bool DeQueue(LinkQueue &Q, int &x)
{
    if (Q.front == NULL)
    { // 空队
        return false;
    }
    LinkNode *q = Q.front; // p指向此次出队的节点
    x = q->data;           // 用变量x返回队头元素
    Q.front = q->next;     // 修改front指针
    if (Q.rear == q)
    {                   // 此次是最后一个节点出队
        Q.front = NULL; // front指向NULL
        Q.rear = NULL;  // rear 指向NULL
    }
    free(q); // 释放节点空间
    return true;
}